package com.arron.algorithm.leetcodetop100.二叉树;

import com.arron.algorithm.tree.TreeNode;
import com.arron.jvm.ref.StrongRefDemo;

public class 二叉树的最近公共祖先 {


    //分类讨论
    // 1,如果两个节点是在root 两边，则直接返回root
    // 2，如果两个节点在同一颗子树上，则返回 离根节点最近的那个节点p ,或者q

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null){
            return null;
        }
        if (root == p || root ==q){
            return root;
        }

        //递归去左子树找
        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        //递归去右子树找
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);


        //在左子树中找到了p ,q
        if (leftNode != null && rightNode ==null){
            return leftNode;
        }
        //在右子树中找到了p ,q
        if (leftNode == null && rightNode !=null){
            return rightNode;
        }

        //两边都找不到 直接返回 null;
        if (leftNode == null && rightNode  ==null){
            return null;
        }

        //在两边都能找到 q，p节点，则直接返回根节点
        return root;

    }

    public void dfs(TreeNode root){

        if (root == null){
            return;
        }

        dfs(root.left);
        dfs(root.right);

    }

}
